package leetcode.code2438;

public class Solution {

	int mod = (int) 1e9 + 7;

	public int[] productQueries(int n, int[][] queries) {
		int len = Integer.bitCount(n);
		int[] pows = new int[len];
		int p = 0, pi = 0;
		while (n > 0) {
			if ((n & 1) == 1) {
				pows[pi++] = p;
			}
			n >>= 1;
			p++;
		}
		int[] sums = new int[len + 1];
		for (int i = 1; i <= len; i++) {
			sums[i] = sums[i - 1] + pows[i - 1];
		}
		int[] f = new int[sums[len] + 1];
		f[0] = 1;
		long s = 1;
		for (int i = 1; i < f.length; i++) {
			s = (s << 1) % mod;
			f[i] = (int) s;
		}
		int[] ans = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			int l = queries[i][0], r = queries[i][1];
			ans[i] = f[sums[r + 1] - sums[l]];
		}
		return ans;
	}
}
